package com.zj.leetcode.medium.greed;

import java.util.Arrays;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 下一个更大元素 II
 * 503 next-greater-element-ii
 * @author: Zhang Bo
 * @create: 2022-04-15 10:36:23
 **/
public class NextGreaterElementIi {
    public static void main(String[] args) {
//        int[] nums = {1,2,3,4,3};
        int[] nums = {100, 1, 11, 1, 120, 111, 123, 1, -1, -100};
        Solution solution = new NextGreaterElementIi().new Solution();

        System.out.println(Arrays.toString(solution.nextGreaterElements(nums)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int[] nextGreaterElements(int[] nums) {
            int sub = 0;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > max) {
                    sub = i;
                    max = nums[i];
                }
            }


            int[] sorts = new int[nums.length];
            int j = 0;
            for (int i = sub + 1; i < nums.length; i++) {
                sorts[j] = nums[i];
                j++;
            }

            for (int i = 0; i < sub + 1; i++) {
                sorts[j] = nums[i];
                j++;
            }


            Stack<Integer> stack = new Stack<>();

            int[] sortRet = new int[sorts.length];
            for (int i = 0; i < sorts.length; i++) {
                while (!stack.isEmpty() && stack.peek() < sorts[i]) {
                    sortRet[stack.pop()] = sorts[i];
                }
            }

            System.out.println(Arrays.toString(sortRet));

            int[] ret = new int[sortRet.length];
            int k = 0;
            for (int i = sorts.length - sub - 1; i < sortRet.length; i++) {
                ret[k] = sortRet[i];
                k++;
            }

            for (int i = 0; i < sorts.length - sub - 1; i++) {
                ret[k] = sortRet[i];
                k++;
            }

            return ret;

        }


        /**
         * 循环数组 就是复制一遍原数组然后拼接在尾部
         * @param nums
         * @return
         */
        public int[] nextGreaterElements01(int[] nums) {
            int n = nums.length;
            int [] res = new int[n];
            Arrays.fill(res, -1);
            Stack <Integer> stack = new Stack<>();
            for (int i = 0; i < n*2; i++){
                int num = nums[i % n];
                while(!stack.isEmpty() && num > nums[stack.peek()]){
                    res[stack.pop()] = num;
                }
                if(i < n) stack.add(i);
            }
            return res;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}
